package main

import "strconv"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func binaryTreePaths(root *TreeNode) []string {
	result := []string{}
	var dfs func(n *TreeNode, p string)
	dfs = func(n *TreeNode, p string) {
		if n == nil {
			return
		}
		if p == "" {
			p = strconv.Itoa(n.Val)
		} else {
			p = p + "->" + strconv.Itoa(n.Val)
		}
		if n.Left == nil && n.Right == nil {
			result = append(result, p)
			return
		}
		dfs(n.Left, p)
		dfs(n.Right, p)
	}
	dfs(root, "")
	return result
}

func main() {
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Right: &TreeNode{
				Val: 5,
			},
		},
		Right: &TreeNode{
			Val: 3,
		},
	}
	ret := binaryTreePaths(root)
	println(ret)
}